// 第一种,使用排序
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}


// 第二种,使用HashMap
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int len = nums.length / 2;
        for(int num : nums){
            int count = map.getOrDefault(num,0);
            map.put(num,count+1);
            if(map.get(num) > len){
                return num;
            }
        }
        return -1;
    }
}

// 第三种,使用摩尔投票法
class Solution {
    public int majorityElement(int[] nums) {
        int n = 0,vote = 0;
        for(int num: nums){
            if(vote == 0) n = num;
            vote += (num == n ? 1 : -1);
        }
        return n;
    }
}

